package 题目集.动态规划.区间dp;

import java.util.Arrays;
import java.util.Scanner;

/**
 * https://www.acwing.com/problem/content/284/
 * 做这种题首先要想到怎么枚举所有状态
 * 枚举所有的邻居点作为第一次合并。
 * 再在此基础上，枚举所有的第二堆
 * ....
 * 直到最后一堆
 * 总共需要枚举!(n-1)次
 */
public class 石子合并 {

    static int[][] dp;
    static int[] sum;

    public static int dfs(int l, int r) {
        if (l == r) return 0;
        if (dp[l][r] != -1) return dp[l][r];
        int cur = sum[r] - sum[l - 1];  //合并当前堆的代价
        int res = Integer.MAX_VALUE;
        for (int k = l; k < r; k++) {
            int left = dfs(l, k);
            int right = dfs(k + 1, r);
            int curr = (left + right);
            res = Math.min(res, curr);
        }
        dp[l][r] = res + cur;
        return dp[l][r];
    }

    /**
     * dp[l][r]：合并l..r区间的方案数，取其最小值
     * 可选操作：最后一步合并dp[l][l]+dp[l+1][r]，最后一步合并dp[l][l+1]+dp[l+2][r]...最后一步合并dp[l][l+k]+dp[r][r]的方案
     * 递归边界：l==r。
     * 递推关系：dp[x][x]->dp
     * @param n
     * @return
     */
    public static int dpFun(int n) {
        int[][] dp = new int[n + 1][n + 1];
        for (int len = 1; len <= n; len++) {    //枚举长度
            int l = 1;
            int r = l + len;
            while (r <= n) {
                dp[l][r] = Integer.MAX_VALUE;
                for (int k = l; k < r; k++) {
                    dp[l][r] = Math.min(dp[l][r], dp[l][k]+dp[k + 1][r]);
                }
                dp[l][r] += sum[r] - sum[l - 1];
                l++;
                r++;
            }
        }
        return dp[1][n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sum = new int[n + 1];
        dp = new int[n + 1][n + 1];
        for (int[] ints : dp) {
            Arrays.fill(ints, -1);
        }

        for (int i = 1; i < sum.length; i++) {
            sum[i] = sc.nextInt() + sum[i - 1];
        }
//        int dfs = dfs(1, n);
//        System.out.println(dfs);
        int i = dpFun(n);
        System.out.println(i);
    }
}
